#include "graph.hpp"
#include "random.hpp"
#include "error.hpp"
#include <cstring>
#include <cctype>
#include <fstream>
#include <string>
#include <algorithm>

graph_c::~graph_c ( void )
{
        if ( NULL != sorted_edges )
        {
                for ( edges_v2::iterator i = sorted_edges->begin (); i != sorted_edges->end (); i ++ )
                {
                        delete ( edges_v * ) * i;
                }
                delete sorted_edges;
        }

        if ( NULL != edges )
        {
                for ( edges_v::iterator i = edges->begin (); i != edges->end (); i ++ )
                {
                        delete ( edge_c * ) * i;
                }
                delete edges;
        }
}

graph_c::graph_c ( long nodes_count, long edges_count, double density, problem_type_e problem_type ) :
        problem_type    ( problem_type ),
        nodes_count     ( nodes_count ), 
        max_edges_count ( edges_count ),
        density         ( density ),
        edges           ( NULL ),
        sorted_edges    ( NULL )
{
        throw_if ( nodes_count <= 0 || max_edges_count < 0, ERROR_INVALID_ARGUMENTS );
        edges = new edges_v () ;
        edges->reserve ( edges_count );

        sorted_edges = new edges_v2 ();
        for ( long i = 0; i < nodes_count - 1; i ++ )
        {
                edges_v * edges = new edges_v ( nodes_count - 1 - i, NULL );
                sorted_edges->push_back ( edges );
        }
}

graph_c::graph_c ( const graph_c & right ) :
        problem_type    ( UNDEFINED ),
        nodes_count     ( -1 ),
        max_edges_count ( -1 ),
        density         ( -1.0 ),
        edges           ( NULL ),
        sorted_edges    ( NULL )
{
        throw ERROR_UNIMPLEMENTED;
}

bool graph_c::edge_already_exists ( const edge_c * edge ) const
{
        for ( edges_v::iterator i = edges->begin (); i != edges->end (); i ++ )
        {
                if ( * ( edge_c * ) * i == * edge )
                        return true;
        }
        return false;
}

void graph_c::add_edge ( edge_c * edge )
{
        throw_if ( edges->size () >= ( unsigned long ) max_edges_count, ERROR_STATE_UNEXPECTED );
        throw_if ( edge_already_exists ( edge ), ERROR_EDGE_ALREADY_EXISTS );
        throw_if ( ! edge->is_valid (), ERROR_INVALID_EDGE );
        throw_if ( ! edge->is_normalized (), ERROR_UNNORMALIZED_EDGE );
        
        edges->push_back ( edge );
        trace( TRACE_LEVEL_LOW,
               "%d %d %f %d\n", 
               edge->get_first_node_id (), 
               edge->get_second_node_id (), 
               edge->get_probability (), 
               edge->is_rigid () );
}

graph_c * graph_c::parse_dimacs_problem ( std::istream & stream )
{
        const char      format_expected_pedge [] = "pedge";
        const char      format_expected_edge  [] = "edge";
        const size_t    format_buffer_size = sizeof ( format_expected_pedge );
        std::string     format ( format_buffer_size, '\0' );

        stream.width ( format_buffer_size );
        stream >> format;
        std::transform ( format.begin (), format.end (), format.begin (), tolower );
        problem_type_e problem_type = UNDEFINED;

        if ( 0 == strncmp ( format_expected_pedge, format.c_str (), format_buffer_size ) )
        {
                problem_type = PEDGE;
        }
        else if ( 0 == strncmp ( format_expected_edge, format.c_str (), format_buffer_size ) )
        {
                problem_type = EDGE;
        }
        else
                throw ERROR_INVALID_INPUT;

        long nodes_count = -1, edges_count = -1;
        stream >> nodes_count >> edges_count;
        throw_if ( nodes_count <= 0 || edges_count < 0, ERROR_INVALID_INPUT );

        graph_c * graph = new graph_c ( nodes_count, edges_count, -1.0, problem_type );
        return graph;
}

edge_c * graph_c::parse_dimacs_edge ( std::istream & stream, problem_type_e problem_type )
{
        edge_c * edge = new edge_c ();
        edge->parse ( stream, PEDGE == problem_type );
        return edge;
}

graph_c* graph_c::parse_dimacs ( std::istream & stream )
{
        graph_c * graph = NULL;

        try
        {
                while( stream.good () )
                {
                        std::string dump_buffer;
                        char line_type = '\0';
                        stream >> line_type;
                        line_type = tolower ( line_type );

                        switch ( line_type )
                        {
                                case 'c':      
                                        std::getline ( stream, dump_buffer );
                                        break;
                                case 'p':
                                        graph = parse_dimacs_problem ( stream );
                                        break;
                                case 'e':
                                        throw_if ( NULL == graph, ERROR_INVALID_INPUT );
                                        throw_if ( UNDEFINED == graph->problem_type, ERROR_STATE_UNEXPECTED );

                                        edge_c * edge = parse_dimacs_edge ( stream, graph->problem_type );
                                        edge->normalize ();
                                        graph->add_edge ( edge );
                                        break;
                        }
                }
        }
        catch ( error_e error_code )
        {
                throw error_code;
        }
        catch ( ... )
        {
                throw ERROR_IO;
        }

        long edges_count = graph->get_edges_count ();
        long nodes_count = graph->get_nodes_count ();
        graph->density = 2 * edges_count / nodes_count * ( nodes_count - 1 );
        graph->sort_edges ();
        
        return graph;
}

graph_c* graph_c::parse_dimacs ( const char * file_path )
{
        throw_if ( NULL == file_path, ERROR_INVALID_ARGUMENTS );

        std::filebuf file_buffer;
        throw_if ( NULL == file_buffer.open ( file_path, std::ios::in ), ERROR_IO );
        
        std::istream stream ( & file_buffer );
        graph_c * graph = parse_dimacs ( stream );
        
        file_buffer.close ();
        return graph;
}

graph_c * graph_c::generate_random ( long nodes_count, 
                                     long rigid_edges_count, 
                                     double density, 
                                     const distribution_i & probabilities_distribution )
{
        throw_if ( density < 0.0 || density > 1.0, ERROR_INVALID_ARGUMENTS );
        
        const long      complete_graph_edges_count   = nodes_count * ( nodes_count - 1 ) / 2;
        const long      edges_count                  = density * complete_graph_edges_count;
        const long      soft_edges_count             = edges_count - rigid_edges_count;
        const long      missing_edges_count          = complete_graph_edges_count - edges_count;

        probabilities_v * probabilities = new probabilities_v ();
        probabilities->reserve ( edges_count ); 
        for ( long i = 0; i < soft_edges_count; i ++ )
        {
                double probability = probabilities_distribution.next ();
                probabilities->push_back ( probability );
        }
        for ( long i = 0; i < rigid_edges_count; i ++ )
        {
                probabilities->push_back ( 1.0 );
        }
        for ( long i = 0; i < missing_edges_count; i ++ )
        {
                probabilities->push_back ( 0.0 );
        }
        
        throw_if ( ( unsigned long ) complete_graph_edges_count != probabilities->size (), ERROR_STATE_UNEXPECTED );
        std::random_shuffle ( probabilities->begin (), probabilities->end () );

        graph_c * graph = new graph_c ( nodes_count, edges_count, density, PEDGE );
        probabilities_v::iterator probabilities_iterator = probabilities->begin ();
        for ( long i = 1; i <= nodes_count - 1; i ++ )
        {
                for ( long j = i + 1; j <= nodes_count; j ++ )
                {
                        throw_if ( probabilities->end () == probabilities_iterator, ERROR_STATE_UNEXPECTED );

                        double probability =  ( double ) * probabilities_iterator;
                        
                        if ( probability > 0.0 )
                        {
                                edge_c * edge = new edge_c ( i, j, probability );
                                graph->add_edge ( edge );
                        }

                        probabilities_iterator ++;
                }
        }
        
        probabilities->clear ();
        delete probabilities;

        graph->sort_edges ();
        return graph;
}

long graph_c::get_nodes_count ( void ) const
{
        return nodes_count;
}

long graph_c::get_edges_count ( void ) const
{
        return edges->size ();
}

long graph_c::get_max_edges_count ( void ) const
{
        return max_edges_count;
}

const edge_c * graph_c::get_edge ( long first_node_id, long second_node_id ) const
{
        throw_if ( first_node_id >= second_node_id, ERROR_INVALID_ARGUMENTS );
        return sorted_edges->at ( first_node_id - 1 )->at ( second_node_id - first_node_id - 1 );
}

void graph_c::store_dimacs ( std::ostream & stream ) const
{
        try
        {
                stream << "c Autogenerated by robust-ant" << std::endl;
                stream << "c Graph is ready for robust colouring problem" << std::endl;
                stream << "p pedge " << nodes_count << ' ' << edges->size () << std::endl;
                stream.setf ( std::ios::fixed, std::ios::floatfield );
                for ( edges_v::const_iterator i = edges->begin (); i != edges->end (); i ++ )
                {
                        const edge_c * edge = ( edge_c * ) * i;
                        stream << "e " << edge->get_first_node_id () << ' ' 
                               << edge->get_second_node_id () << ' '
                               << edge->get_probability () << std::endl;
                }
        }
        catch ( ... )
        {
                throw ERROR_IO;
        }
}

void graph_c::store_dimacs ( const char * file_path ) const
{
        throw_if ( NULL == file_path, ERROR_INVALID_ARGUMENTS );

        std::filebuf file_buffer;
        throw_if ( NULL == file_buffer.open ( file_path, std::ios::out ), ERROR_IO );
        
        std::ostream stream ( & file_buffer );
        store_dimacs ( stream );
        
        file_buffer.close ();
}

void graph_c::sort_edges ()
{
        for ( edges_v::iterator i = edges->begin (); i != edges->end (); i ++ )
        {
                edge_c * edge = ( edge_c * ) * i;
                long j = edge->get_first_node_id ();
                long k = edge->get_second_node_id ();
                sorted_edges->at ( j - 1 )->at ( k - j - 1 ) = edge;
        }
}

